﻿//二叉树进阶
//二叉搜索树
//二叉排序树
//性质：
//左子树值小于根，右子树值大于根、
// （找小向左找，找大向右找）
// 
//
#include<string>
#include"searchbt.h"

/*
int main()
{
	int a[] = { 8,3,1,10,6,4,7,14,13 };
	BSTree<int> t;
	for (auto e : a)
	{
		t.Insert(e);
	}

	//传根
	//t.InOrder(t._root);//❌传根有问题：一般来说根节点是私有
	//换种方式，函数也放私有，再用一个共有的函数去复用（调用私有）（不传参）

	t.InOrder();
	//查找排序++去重
	//就用一遍InOrder(),默认找到一样的数据key不进行插入

	//最坏的情况下（树极度不平衡，只有左树，没有右节点），增删拆改的效率很低
	//引入（平衡二叉搜索树）AVL树，红黑树

	//先删除4再删除3就构建出了场景：右树最小就是这个第一个只有右树的节点
	t.Erase(4);
	t.Erase(3);
	t.InOrder();

	//最好全部删除一遍，检察仔细
	for (auto e : a)
	{
		t.Erase(e);
		t.InOrder();
		//删到崩溃了：原因：删了一边之后，还剩另一边子树，可是这时候要删除树根，数个没有父亲节点，就找不到，溢出
	//特殊处理：_root,挪一下位置
	}

	return 0;
}
*/

//key/value的场景

//
//int main()
//{
//	keyValue::BSTree<string, string> dict;//字典
//	dict.Insert("left", "左边");
//	dict.Insert("string", "字符串");
//	dict.Insert("string1", "字符串1");
//	dict.Insert("string2", "字符串2");
//	dict.Insert("string3", "字符串3");
//
//	string str;
//	while (cin >> str)//有流插入就进入循环
//	{
//		auto ret = dict.Find(str);//找
//		if (ret)//找到了
//		{
//			cout << "->" << ret->_value << endl;//输出
//		}
//		else
//		{
//			cout << "没有这个单词，请重新输入：" << endl;
//		}
//	}
//	//while (cin >> str)
//	//结束这个程序，ctrl C（暴力）
//	//ctrl Z + enter
//
//	return 0;
//}

//统计次数
/*
int main()
{
	string arr[] = { "苹果","西瓜","西瓜","苹果","西瓜","香蕉"};
	keyValue::BSTree<string, int> countTree;
	for (const auto& str : arr)
	{
		auto ret = countTree.Find(str);//这是在树中第一次找到的地址
		if (ret == NULL)//如果，没有出现过，就插入（是第一次出现）
		{
			countTree.Insert(str, 1);//第一次
		}
		else//不是第一次
		{
			ret->_value++;//出现过了，那么这个找到的ret就应该将它的（从第一次找到返回的ret节点的value）节点的value++
		    //出现多少次，这个节点的value就被+到多少次
		}

	}
	//苹果 2 西瓜 3 香蕉 1
	countTree.InOrder();

	return 0;
}
*/





















